package datastruct.graph;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 邻接链表表示的图
 */

public class AdjcentLinkGraph {

    ArrayList<ArrayList<Integer>> adjLink = new ArrayList<>();

    public AdjcentLinkGraph(ArrayList<ArrayList<Integer>> adjLink){
        this.adjLink = adjLink;
    }

    /**
     * 用入度递减法(BFS)拓扑排序
     * @return 如果不存在拓扑排序返回空数组
     */
    public int[] topoSortByBfs(ArrayList<ArrayList<Integer>> adjLink){
        int vNum = adjLink.size();
        //1，从邻接链表得到入度
        int[] indegree = new int[vNum];
        for (ArrayList<Integer> adjVerts:adjLink) {
            for (int adjVert: adjVerts) {
                indegree[adjVert]++;
            }
        }
        //2，找入度为0的点开始
        int[] res = new int[vNum]; //存放拓扑排序结果
        int count = 0; //记录已排序顶点数
        Stack<Integer> deg0Vert = new Stack<>(); //保存当前入度0的节点
        for (int i = 0; i < vNum; i++) {
            if(indegree[i]==0) deg0Vert.push(i);
        }
        while (!deg0Vert.isEmpty()){
            int vert = deg0Vert.pop();
            res[count++] = vert;
            //vert相邻节点入度都-1
            for (int adj: adjLink.get(vert)) {
                if(--indegree[adj]==0) deg0Vert.push(adj);
            }
        }
        if(count<vNum) return null;
        return res;
    }

    /**
     * 用DFS拓扑排序
     * @return 如果不存在拓扑排序返回空数组
     */
    public int[] topoSortByDfs(ArrayList<ArrayList<Integer>> adjLink){
        int n = adjLink.size();
        int[] status = new int[n];
        Stack<Integer> stack = new Stack<>();
        boolean flag = true; //发现有环就停止
        for (int i = 0; i < n; i++) {
            flag &= dfs(adjLink,status,i,stack);
            if(!flag) return new int[0];
        }
        //stack中保存的是拓扑排序的逆序
        int[] res = new int[n];
        int count = 0;
        while (!stack.empty()){
            res[count++] = stack.pop();
        }
        return res;
    }

    /**
     *
     * @param adjLink 邻接链表
     * @param status 0表示未访问过，-1表示已加入拓扑排序结果，1表示正在搜索
     * @param curNode 当前搜索的节点
     * @param stack 保存搜索完成的节点
     */
    public boolean dfs(ArrayList<ArrayList<Integer>> adjLink, int[] status, int curNode, Stack<Integer> stack){
        if(status[curNode]==1) return false;
        if(status[curNode]==-1) return true;
        status[curNode] = 1;
        boolean flag = true;
        for (int v: adjLink.get(curNode)) {
            flag &= dfs(adjLink,status,v,stack);
            if(!flag) break;
        }
        //发现环
        if(!flag) return false;
        //相邻节点没有环
        status[curNode] = -1;
        stack.push(curNode);
        return true;
    }

    // TODO: 2021/8/12 用并查集和dfs\bfs求连通分支数 
    public int component(){
        return 0;
    }
}
